package com.zwj.interview.单调栈;

import java.util.Arrays;
import java.util.Iterator;
import java.util.Stack;

/**
 * @Author: Zwj
 * @Date: 2022/9/15 16:06
 * 输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1
 * 比如说，输入一个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。
 * 因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4;
 * 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1
 *
 * 单调栈:
 从数组的最后一位开始遍历
   [2,1,2,4,3]
  ①：此时栈为空，比3大的置为-1,3直接入栈
  ②：此时栈中为3,4大于3，栈顶的3弹出来，此时栈为空，那么比4大的数为-1，4入栈
  ③：此时栈中为4,2比4小，那么比2大的就是栈顶的4,2入栈
  ④：此时栈中为2,4,那么1比2小，比1大的数就是2,1入栈
  ⑤：此时栈中为1,2,4，那么2比1大，2等于2，此刻栈中1,2弹出去，剩下4,2小于4,那么大于2的值为4,2入栈
  ⑥：最后栈中的数字就为:2,4

 */
public class 下一个最大的元素 {

    //寻找下一个数字一般都是往后遍历
   static  int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        // 倒着往栈里放
        for (int i = n - 1; i >= 0; i--) {
            // 栈顶元素小于当前元素，那么直接弹出栈顶元素
            while (!s.isEmpty() && s.peek() <= nums[i]) {
                // 矮个起开，反正也被挡着了。。。
                s.pop();
            }
            // nums[i] 身后的更大元素
            res[i] = s.isEmpty() ? -1 : s.peek();
            s.push(nums[i]);
        }
        return res;
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreaterElement(new int[]{2,1,2,4,3})));
    }



}